/**
 * 
 */
package recursion.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class UniqueBinarySearchTreesII {

	/**
	Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

	For example,
	Given n = 3, your program should return all 5 unique BST's shown below.

	1         3     3      2      1
	\       /     /      / \      \
	 3     2     1      1   3      2
	/     /       \                 \
	2     1         2                 3
	 */
	public ArrayList<TreeNode> generateTrees(int n) {
		return generateTree(1, n);
	}

	public ArrayList<TreeNode> generateTree(int start, int end) {
		ArrayList<TreeNode> result = new ArrayList<TreeNode>();
		if (start > end) {
			result.add(null);
			return result;
		}

		for (int i = start; i <= end; i++) {
			ArrayList<TreeNode> leftNodes = generateTree(start, i - 1);
			ArrayList<TreeNode> rightNodes = generateTree(i + 1, end);
			for (int l = 0; l < leftNodes.size(); l++) {
				for (int r = 0; r < rightNodes.size(); r++) {
					TreeNode node = new TreeNode(i);
					node.left = leftNodes.get(l);
					node.right = rightNodes.get(r);
					result.add(node);
				}
			}
		}
		return result;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
			left = null;
			right = null;
		}
	}

	/**
	 * 
	 */
	public UniqueBinarySearchTreesII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
